package com.pan.alg.basic.sortbasic;


import org.apache.commons.lang3.ArrayUtils;

/**
 * 插入排序的思路
 * 使用双层循环，
 * 外层循环对除了第一个元素之外的所有元素，
 * 内层循环对当前元素前面有序表进行待插入位置查找，并进行移动
 *
 * 1、选定一个数arr[i]
 * 2、用arr[i]与arr[i]之前的数进行对比，如果arr[i]大，不用移动，如果arr[i]小，向前移动。
 *
 * 和选择排序相比，优势在于可以提前终止第二层循环。
 */
public class InsertionSort{

    // 我们的算法类不允许产生任何实例
    private InsertionSort(){}

    public static void sort(Comparable[] arr){

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            //复制第i个元素值
            Comparable e = arr[i];
            //保存元素e应该插入的位置
            int j = i;
            for( ; j > 0 && arr[j-1].compareTo(e) > 0 ; j--)
                arr[j] = arr[j-1];
            arr[j] = e;
        }
    }

    /**
     * 下标的选择十分的重要，下面这个写法也正确，但是看起来就复杂很多，且难以理解
     * 从小到大排序
     * @param arr
     */
    public static void mysort(Integer[] arr){
        int length = arr.length;

        for(int i=1;i<length;i++){
            int e = arr[i];
            int j=i-1;
            for(;j>=0&&arr[j]>e;j--){
                arr[j+1]=arr[j];
            }
            //如果元素有移动，才进行赋值
            if(j<i-1){
                //如果是第0个元素，直接赋值即可。
                if(j==0){
                    arr[0]=e;
                }else {
                    arr[j+1]=e;
                }
            }
            System.out.println(ArrayUtils.toString(arr));
        }
    }

    /**
     * 简单示例
     * @param arr
     */
    //{4,3,6,7,8,9,4,2,11,23,56,43,45}
    public static void insertSort(int[] arr){

        int length = arr.length;
        for(int i=0;i<length;i++){
            int temp = arr[i];
            int j=i;
            for(;j>0;j--){
                if(temp<arr[j-1]){
                    arr[j]=arr[j-1];
                }else{
                    break;
                }
            }
            arr[j]=temp;
        }
    }

    // 测试 InsertionSort
    public static void main(String[] args) {

//        int N = 20;
//
//        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100);
//        System.out.println(ArrayUtils.toString(arr));
        //
        Integer[] arrT = {32,99,25,52,11,59,25,36,53,0,47,0,36,46,53,3,0,44,79,84};

        mysort(arrT);
        //SortTestHelper.testSort("bobo.algo.InsertionSort", arr);
        //sort(arrT);
        System.out.println(ArrayUtils.toString(arrT));

    }
}